package Sort;

import java.util.Arrays;

public class QuickSort {
    /* 元素交换 */
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /* 哨兵划分 */
    public int partition(int[] nums, int left, int right) {
        // 以 nums[left] 为基准数
        int i = left, j = right;
        while (i < j) {
            // 从右向左找第一个小于基准数的元素
            while (i < j && nums[j] >= nums[left]) {
                j--;
            }
            // 从左向右找第一个大于基准数的元素
            while (i < j && nums[i] <= nums[left]) {
                i++;
            }
            swap(nums, i, j);
        }
        swap(nums, i, left);
        return i;
    }

    /* 快速排序 */
    public void quickSort(int[] nums, int left, int right) {
        // 子数组长度为 1 时终止递归
        // 注意传入的始终是原数组，因此不能用数组长度作为判断条件
        if (left >= right)
            return;
        // 哨兵划分
        int pivot = partition(nums, left, right);
        System.out.print("pivot1 的值为" + pivot + "   ");
        // 递归左子数组、右子数组
        quickSort(nums, left, pivot - 1);
        quickSort(nums, pivot + 1, right);
    }

    /* 快速排序（尾递归优化） */
    public void quickSortPlus(int[] nums, int left, int right) {
        // 子数组长度为 1 时终止
        while (left < right) {
            // 哨兵划分操作
            int pivot = partition(nums, left, right);
            System.out.print("pivot2 的值为" + pivot + "   ");
            // 对两个子数组中较短的那个执行快速排序
            if (pivot - left < right - pivot) {
                quickSort(nums, left, pivot - 1); // 递归排序左子数组
                left = pivot + 1; // 剩余未排序区间为 [pivot + 1, right]
            } else {
                quickSort(nums, pivot + 1, right); // 递归排序右子数组
                right = pivot - 1; // 剩余未排序区间为 [left, pivot - 1]
            }
        }
    }

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        // int[] nums = { 10, 45, 43, 2, 34, 3, 2, 54 };
        int[] nums = { 4, 5, 8, 7, 6, 3, 9 };
        quickSort.quickSort(nums, 0, nums.length - 1);
        System.out.println();
        int[] nums1 = { 4, 5, 8, 7, 6, 3, 9 };
        quickSort.quickSortPlus(nums1, 0, nums1.length - 1);
        System.out.println();
        System.out.println(Arrays.toString(nums));
    }
}
